#include<iostream>

using namespace std;
/*const int N = 40;
int ans[N][N];
int n;
bool col[N],dg[N],udg[N];
int _count;
int flag=3;

void dfs(int u)
{
	if(u == n)
	{
		_count++;
		
		if(flag>0)
		{
			for(int i=0;i<n;i++)
				{
					cout<<ans[u][i]<<" ";
				}
			cout<<endl;
			flag--;
		}
		return ;
	}
	for(int i=0;i<n;i++)
	{
		if(!col[i]&&!dg[n+i]&&!udg[n+i-u])
		{
			ans[u][i]=i;
			col[i]=dg[n+i]=udg[n+i-u]=true;
			dfs(u+1);
			//ans[u]=i; 
			col[i]=dg[n+i]=udg[n+i-u]=false;
		}
	}
}


int main()
{
	cin>>n;
	dfs(0);
	cout<<_count;
	return 0;
}*/




#include<iostream>

using namespace std;
const int N = 50;
int ans[N];
int n;
bool col[N], dg[N], udg[N];
int _count=0;
int flag = 3;

void dfs(int u)
{
	if (u == n)
	{
		_count++;

		if (flag > 0)
		{
			for (int i = 0; i < n; i++)
			{
				cout << ans[i] << " ";
			}
			cout << endl;
			flag--;
		}
		return;
	}
	for (int i = 1; i <= n; i++)
	{
		if (!col[i] && !dg[u + i] && !udg[u-i+n])
		{
			ans[u] = i;
			col[i] = dg[u + i] = udg[n - i  +u] = true;
			dfs(u + 1);
			//ans[u]=i; 
			col[i] = dg[u + i] = udg[n - i  +u] = false;
		}
	}
}


int main()
{
	cin >> n;
	dfs(0);
	cout << _count;
	return 0;
}


